# coding=utf-8
__author__ = 'st316'
'''
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
'''


# Definition for a point
class Point:
    def __init__(self, a=0, b=0):
        self.x = a
        self.y = b


class Solution:
    # @param points, a list of Points
    # @return an integer
    def maxPoints(self, points):
        n = 0
        for i in xrange(len(points)):
            d = {}
            num = 1
            curMax = 0
            for j in xrange(i + 1, len(points)):  # 只计算之后的点，之前的固定的直线已经算过
                if self.eq(points[i], points[j]):
                    num += 1
                else:
                    k = self.slope(points[i], points[j])
                    if k in d:
                        d[k] += 1
                    else:
                        d[k] = 1
                    if d[k] > curMax:
                        curMax = d[k]
            curMax += num
            n = max(curMax, n)
        return n

    def eq(self, p1, p2):
        return p1.x == p2.x and p1.y == p2.y

    def slope(self, p1, p2):
        # return # if k infinitely great
        if p1.x == p2.x:
            return '#'
        else:
            return float(p1.y - p2.y) / (p1.x - p2.x)


if __name__ == '__main__':
    p1 = Point(0, 0)
    p2 = Point(0, 0)
    s = Solution()
    print s.maxPoints([p1, p2])

